package leetcode_100;

/**
 *@author 周杨 
 *RotateList_61 反转链表 
 *describe: 1:k小于链表长度  用哨兵监控在哪里反转  2:k大于链表长度  递归调用自己 AC 96%
 *2018年5月10日 下午2:50:38
 */
public class RotateList_61 {
	static class ListNode{
		int val;
		ListNode next;
		ListNode(int x) { val = x; }
	}
	ListNode res;
	public static void main(String[] args) {
		RotateList_61 test=new RotateList_61();
		ListNode a=new ListNode(1);
		ListNode b=new ListNode(2);
		ListNode c=new ListNode(3);
		ListNode d=new ListNode(4);
		ListNode e=new ListNode(5);
		a.next=b;
		b.next=c;
		c.next=d;
		d.next=e;
		test.rotateRight(a, 2);

	}
	
	public ListNode rotateRight(ListNode head, int k) {
		if(k==0) {
			this.res=head;
			return res;
		}
		if(head==null)
			return null;
		ListNode pre=head,run=head;
		int count=1,judge=0;
		while(run.next!=null) {
			if(judge==k) {
				pre=pre.next;
			}
			else {
				++judge;
			}
			run=run.next;
			++count;
		}
		if(count<=k) {//个数太少
			k=k%count;
			return rotateRight(head, k);
		}
		run.next=head;
		this.res=pre.next;
		pre.next=null;
        return this.res;
    }

}
